This invention relates to methods for fitting logic cells in an electronic design. More specifically, the invention relates to the use of hardware to perform the fitting function during design of an electronic product.
During the design phase of a new electronic product (e.g., an integrated circuit), logic functions must be designed, tested, and ultimately laid-out on a substrate (e.g., silicon or other semiconductor). The layout component of this process typically involves placement of logic blocks at specified locations on the substrate and routing lines between the various logic blocks on the substrate. These functions are generically referred to as xe2x80x9cplace and route.xe2x80x9d
In some electronic productsxe2x80x94notably some programmable logic devicesxe2x80x94the layout of logic on the substrate assumes a hierarchy. In this hierarchy, fundamental units of logic may be referred to as logic cells or logic elements. These logic cells may be grouped into larger blocks of logic that may be referred to as xe2x80x9clogic array blocksxe2x80x9d for example. These blocks of logic may, in turn, be grouped into rows and ultimately columns on the hardware device.
In such xe2x80x9chierarchicalxe2x80x9d electronic designs, the place and route design function may be supplemented by a xe2x80x9cpartitioningxe2x80x9d function in which lower level logic elements (e.g., logic cells) are grouped into larger logic blocks (e.g., logic array blocks). It is these logic blocks that are then placed on the substrate in a manner analogous to a conventional placement operation in place and route. Lines between the logic blocks are then routed in a conventional routing fashion. Collectively, partitioning and place and route are referred to as xe2x80x9cfittingxe2x80x9d operations.
Modem tools for designing electronic products are implemented as software. This software may allow the designer to specify the desired functioning of the end device, as well as some architectural and logic constraints. The software tools can take this information and, with the designer""s aid, develop Boolean, schematic, and ultimately hardware designs. In the design process, the software fits the logic onto the hardware device to provide the final design layout.
Typically the design software xe2x80x9ccompilesxe2x80x9d a design to produce a hardware layout. Compilation takes as an input a user""s specifications (including high and low level logic constraints, timing requirements, etc.) and then synthesizes that design and fits it onto a target hardware device. In the case of programmable devices, the resulting compiled electronic design is then used to program a blank (unprogrammed) device. Designs for application specific integrated circuits, including programmable logic devices and field programmable gate arrays, as well as non-programmable electronic devices such as gate arrays all may require compilation involving synthesis of logic functions and fitting.
Commonly the fitting operations occupy the vast majority of the compile time. For example, in some programmable logic devices, the partitioning operation can occupy as much as four-fifths of the time to compile a design. This is true even when the compiler uses xe2x80x9cfastxe2x80x9d algorithms which do not try each and every possible partition before settling on a xe2x80x9cbestxe2x80x9d partition. Such algorithms often do find the truly best partition from among all possible partitions. However, there are also numerous instances when they converge on a less than optimal partition.
As electronic designs including programmable gate arrays, etc. become larger and more complex, the time required for software tools to compile and perform other design operations is growing rapidly. In fact, compile times increase quadratically with the number of logic gates in a design. For this reason, it is desirable to find methods and mechanisms for increasing the speed at which design tools perform their functions, such as compilation. It would be particularly desirable to find a way to increase the speed at which these tools perform the most computationally expensive tasks such as fitting.
The present invention provides a method and mechanism for speeding the fitting portion of electronic design compilation. Specifically, the invention provides for the use of hardware to perform the computations necessary for fitting an electronic design onto a substrate. This hardware may be used in conjunction with a conventional software design tool which is reserved for performing other design functions such as logic synthesis and technology mapping. In a preferred embodiment, the hardware tool performs the steps necessary to partition logic cells into logic blocks for use in a hierarchical electronic design. In a particularly preferred embodiment, the hardware tool is provided as a product term device which temporarily stores information defining a given partitioning problem and then calculates the quality of the partition for every possible partition employing the constraints of the stored partitioning problem.
One aspect of the invention provides a method of compiling an electronic design. The method may be characterized as performing calculations necessary for fitting on hardware designed or programmed for performing the calculation. Preferably, the hardware includes a plurality of product terms, arranged in an array on a programmable logic device for example. The product terms may be provided on an appropriate configured embedded array block of the programmable logic device.
When product terms are employed, they may store a representationxe2x80x9d of the connections to logic cells via appropriately programmed memory elements on intersection of bitlines and wordlines of the product terms. From this arrangement, the system determines the xe2x80x9cmetricxe2x80x9d of various fitting options for logic elements by controlling values on wordlines to the product terms. This allows the system to determine the best fitting option. This approach is particularly well adapted for determining the best of several the partitions of the logic cells into two or more logic blocks. When the hardware performs partitioning, the each of the wordline or pair of wordlines to the product terms represents a cell that is to be provided in one of two logic blocks. Each product term or pair of product terms represents a signal that is fed to one or more of the cells. Each set of inputs to the wordlines corresponds to a different partition. Multiple partitions of the logic cells to the logic blocks are compared by varying the wordline inputs and measuring the product term outputs. The outputs represent the number of interconnections that must be made to the logic block under consideration (as defined by input values on the wordlines). In some embodiments, determining which partition provides the best fit involves determining which partition has the lowest total number of connections to the logic block. In other embodiments, it involves a further consideration of a balance of connections between the logic blocks of the partitions.
Another aspect of this invention is the hardware device that performs the fitting operation. Such hardware may be characterized as a first product term array configured to (a) provide a representation of connections to a plurality of logic cells and (b) output the number of connections to a first logic block containing a first subset of the plurality of logic cells. The number of connections is determined by a first set of input values to the first product term array which first set of input values represent the first subset of logic cells in the first logic block. As noted, the input values to the product term array may be provided through wordlines to the product term array.
To generate the input values to these wordlines, the hardware device may employ a generation block which defines a plurality of patterns of input values to the product term array, with each pattern specifying a partition of the logic cells into the logic blocks. Preferably, the generation block includes a ROM storing multiple values, each corresponding to a partition of the logic cells into the logic blocks. In a specific embodiment, the generation block contains two ROMs each of which stores values containing a number of bits equal to one-half the number of logic cells in the plurality of logic cells. To count the number of interconnections output by the product term array, the hardware may employ an adder block (e.g., a series of adders or a tree of adders) coupled to the product term array, which counts the number of connections output by the product term array.
In a preferred embodiment, the hardware includes a second product term array in addition to the first product term array. The second product term array is configured to (a) provide the representation of connections to the plurality of logic cells (same as in the first product term array) and (b) output the number of connections to a second logic block containing a second subset of the plurality of logic cells. Usually, the second subset of cells will be those cells which were not present in the first subset. In this case, a second set of input values is provided to the second product term, which second set of input values is the compliment of the first set of input values. To quickly calculate the total number of interconnections to each of the logic blocks in a partition, each of the first and second product term arrays may have their outputs coupled to adder blocks, which count the numbers of connections output by the product term arrays. The outputs of these adder blocks may be provided to a summing unit which sums the number of connections output by the adder blocks to provide a total number of connections to the first and second logic blocks. Finally, the hardware may include a storage unit which stores information about the best of a plurality of partitions of the logic cells between the first and second logic blocks.
These and other features and advantages of the present invention will be further described in the following description of the invention in conjunction with the associated figures.